require "benchmark";

class Sort
  
  class << self
    
    def _prepare(array)
      (1..100).to_a.each{|n| n + 2;};
      array.sort;
    end
    
    def rearray(array)
      array.inject([array.shift]) do |array, n|
        array.send((array.last >= n) ? :unshift : :push, n);
        array;
      end
    end
    
    def bubble(array)
      swapped = true;
      size = array.size;
      while swapped
        swapped = false;
        (size -= 1).times do |n|
          if array[n] > array[n + 1]
            array[n], array[n + 1] = array[n + 1], array[n];
            swapped = true;
          end
        end
      end
      array;
    end
    
    def divide(array, pivot=array.first)
      return array if array.size <= 0;
      less, equal, greater = [], [], [];
      for n in array
        if n < pivot then less << n;
        elsif n == pivot then equal << n;
        else greater << n; end
      end
      divide(less) + equal + divide(greater);
    end
    
    def default(array)
      array.sort{|a, b| a <=> b;};      
    end
    
  end
  
end

Log = Struct.new(:method, :arrays);
Arrays = [[10, 8, 4, 1, 3, 6, 9, 7, 2, 5], [5, 3, 7, 4, 1, 2, 9, 6, 10, 8], [5, 8, 10, 7, 9, 2, 6, 4, 1, 3], [1, 4, 9, 3, 2, 7, 8, 5, 10, 6], [2, 7, 1, 6, 3, 10, 8, 4, 9, 5], [1, 9, 5, 10, 7, 8, 3, 2, 6, 4], [5, 4, 9, 3, 10, 7, 6, 8, 2, 1], [5, 10, 3, 1, 6, 8, 7, 9, 4, 2], [9, 10, 2, 1, 5, 3, 8, 4, 7, 6], [7, 5, 4, 2, 9, 8, 6, 3, 1, 10]];
Logs = [];

Benchmark.bm(15) do |bm|
  
  (Sort.methods - Class.new.methods).sort.each do |sort_alg|
    bm.report("#{sort_alg}") do 
      log = Log.new(sort_alg, []);
      Arrays.each do |array|
        999.times{array = Sort.send(sort_alg, array.dup);};
        log.arrays << array;
      end
      Logs << log;
    end
  end
  
end

Logs.each do |log|
  log.arrays.each do |array|
    raise StandardError, "method #{log.method} didnt sort the array correctly: #{array.inspect}" unless array == (1..10).to_a.sort;  
  end
end
